1. Field of the Invention
Methods and apparatuses consistent with the present invention generally relate to flow service for data packet scheduling, and more particularly, to instant service for deficit-round-robin (DRR) data packet scheduling which is applied to a packet switching network, in which, when a new flow is activated within a service time of a current flow, the new flow is serviced immediately after the service time termination of the current flow and a next flow is serviced according to the flow scheduling.
2. Description of the Related Art
In general, service bandwidths are reserved with respect to a unit of traffic which is called a flow in a packet switching network where data packets are transmitted and received. To guarantee the reserved service bandwidth, the packet switching network applies the bandwidth accurately assigned, to the traffic of a specific flow using a scheduling algorithm. An example of the scheduling algorithm is a deficit round robin (DRR).
The DRR services the active flows in a round-robin manner. For instance, a packet switching device stores each flow of incoming data packets, and a scheduler services the flows in sequence according to the packet scheduling. The packet switching device reads out the data packets in each flow to be serviced from a memory and queues the read data packets. In doing so, a size of the packets to be serviced is compared with a predefined quantum for each flow. When the packet size is smaller than the quantum, the packets are serviced. Next, the packet size is subtracted from the quantum and the resultant value is stored as a deficit counter value. By contrast, when the packet size is greater than the quantum, packets are not serviced but may be serviced in the next round. In the next round, the size of the packets to be serviced is again compared with a summation of a distributed control (DC) value and the quantum value for each flow. When the packet size is smaller than the summation of the DC value and the quantum value, the packets are serviced. When the packet size is greater than the summation of the DC value and the quantum value, the packets are carried forward to the next round.
When servicing the data packets by flows in the DRR, a controller controls the output from an output port according to linked list information stored in a register. The linked list information includes information relating to a header flow, information relating to a tail flow, information relating to service order links between flows, and the like. For instance, as shown in FIG. 1, when a flow 101, a flow 102, a flow 103, a flow 104, and a flow 105 are serviced in sequence from an output of an output port, the flow 101 is designated to the header flow and the flow 105 is designated to the tail flow. The flow 101 is linked to the flow 102 as the next turn, and the flow 102 is linked to the flow 103 as the next turn. The flow 103 is linked to the flow 104 as the next turn, and the flow 104 is linked to the flow 105 as the next turn. The flow 105, which is the tail flow, is linked to the flow 101 being the header flow. The linked list information includes such information, and the controller controls the outputting from the output of the output port according to the linked list information.
In case that a new data packet is input to the packet switching device and a new flow 106 is activated accordingly, the controller designates the new flow 106 to the tail flow and adds it to the linked list information. According to the linked list information, the flow 101, the flow 102, the flow 103, the flow 104, and the flow 105 are serviced in order, and then the new flow 106 is serviced. However, disadvantageously, maximum latency is raised because, if at the moment the flow is activated the flow 101 was being served, the time the flow 106 has to wait for service is unnecessarily large. In this case it can be considered that the penalty is given to the new flow 106 until the other flows are serviced. Thus, the quality of service (QoS) is reduced in the multimedia transmission in the packet switching network.